package simple;

import java.util.HashSet;
import java.util.Set;

/**
 * 编写一个算法来判断一个数 n 是不是快乐数。
 *
 * 「快乐数」定义为：
 *
 * 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
 * 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
 * 如果这个过程 结果为1，那么这个数就是快乐数。
 * 如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
 *
 * 链接：https://leetcode.cn/problems/happy-number
 * @author 胡宇轩
 * @Email: programboy@163.com
 */
public class HappyNumber {
    /**
     * 使用set来判断是否出现重复的数，出现了说明就是死循环了。肯定永远到不了1.
     * 空间复杂度O(logN)
     * */
    class Solution {
        Set<Integer> set = new HashSet<>();
        public boolean isHappy(int n) {
            if(n == 1){
                return true;
            }
            if(set.contains(n)){
                return false;
            }
            set.add(n);
            n = splitNumberAndGetPowerSum(n);
            return isHappy(n);
        }

        private int splitNumberAndGetPowerSum(int n){
            int result = 0;
            while(n != 0){
                int remainder = n % 10;
                result += remainder * remainder;
                n /= 10;
            }
            return result;
        }
    }

    /**
     * 可以将该题抽象成一个链表。因为该题中，下一个数字都依赖上一个数字，也就对应着一个链表
     * 而且有可能数字会重复出现，也就意味着这可能是一个带环链表
     * 所以当出现重复数字时，也就意味着n不是一个快乐数。用快慢指针来查看链表是否带环
     * */
    class Solution1{
        public boolean isHappy(int n) {
            int slow = n;
            int fast = getNext(n);

            while(slow != fast && fast != 1){
                slow = getNext(slow);
                fast = getNext(getNext(fast));
            }
            return fast == 1;
        }

        private int getNext(int n){
            int result = 0;
            while(n != 0){
                int remainder = n % 10;
                result += remainder * remainder;
                n /= 10;
            }
            return result;
        }
    }
}
